import java.util.List;
public class MySingleList implements IList{
    static class ListNode{
        int value;
        ListNode next;

        private ListNode(int value){
            this.value = value;
        }
    }
    public ListNode head;//头节点

    //创建一个链表
    public void createList(){
        ListNode A = new ListNode(1);
        ListNode B = new ListNode(2);
        ListNode C = new ListNode(3);
        ListNode D = new ListNode(4);
        ListNode E = new ListNode(5);
        ListNode F = new ListNode(6);

        this.head = A;
        A.next=B;
        B.next=C;
        C.next=D;
        D.next=E;
        E.next=F;
    }
    //打印链表
    public void display(){
        ListNode cur = head;
        while(cur!=null){
            System.out.print(cur.value+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    //头插
    @Override
    public void addFirst(int data){

            ListNode newN = new ListNode(data);
            newN.next = head;
            head = newN;

    }
    //尾插
    @Override
    public void addLast(int data) {
        ListNode newN = new ListNode(data);
        if(head!=null) {
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newN;
        }else{
            head = newN;
        }
    }

    @Override
    public void addIndex(int data, int index) {
        int len = size();
        if(index<0||index>len){
            System.out.println("位置不合法");
        }else if(index == 0){
            addFirst(data);
        }else if(index == len){
            addLast(data);
        }else{
            int i = 1;
            ListNode cur =head;
            while(i<index){
                cur=cur.next;
                i++;
            }
            ListNode newN = new ListNode(data);
            newN.next = cur.next;
            cur.next = newN;

        }
    }
    //查询是否存在key值
    @Override
    public boolean contain(int key) {
        ListNode cur = head;
        while(cur!=null){
            if(cur.value==key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head ==null){
            return;
        }
        if(head.value==key){
            head = head.next;
            return;
        }
        ListNode node = findNodeOfKey(key);
        if(node==null){
            return;
        }
        node.next = node.next.next;
    }
    //找到需要删除节点的上一个节点
    public ListNode findNodeOfKey(int key){
        ListNode cur = head;
        while(cur.next!=null){
            if(cur.next.value == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    @Override
    public void removeAll(int key) {
        if(head==null){
            return;
        }
        if(head.value==key){
            head = head.next;
        }
        ListNode cur = head;
        ListNode prev = null;
        while(cur.next!=null){
            if(cur.next.value==key){
                cur.next=cur.next.next;
            }
            prev = cur;
            cur=cur.next;
        }
        if(cur.value==key){
            prev.next=null;
        }
    }

    //计算长度
    @Override
    public int size() {
        int length = 0;
        ListNode cur = head;
        while(cur!=null){
            length++;
            cur = cur.next;
        }
        return length;
    }
    //清空
    public void clear(){
        ListNode cur = head;
        while(cur!=null){
            ListNode curN = cur.next;
            cur = null;
            cur = curN;
        }
        head = null;
    }
    //反转链表
    public ListNode reverseList() {
        if(head == null){
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur!=null){
            ListNode curN = cur.next;
            cur.next = head;
            head = cur;
            cur = curN;
        }
        return head;
    }
    public ListNode middleNode() {
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next!=null&&fast!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


}
